// scaup
// (c) 2010, Normen Müller, normen.mueller@gmail.com  
// $Id: Differ.scala 97 2010-08-23 09:00:50Z normen.mueller $
package scaup.text

import java.io.File

/** ASCII differencing options
 *  @author  <a href="mailto:normen.mueller@googlemail.com">Normen M&#xFC;ller</a>
 *  @version 0.0.6
 */
object ASCIIDiffOption extends Enumeration {
  val NORMAL, UNIFIED = Value
}

import scaup.Scaup._
import ASCIIDiffOption._

/** LCS Differencing algorithms
 *  @author  <a href="mailto:normen.mueller@googlemail.com">Normen M&#xFC;ller</a>
 *  @version 0.0.6
 */
object Differ {
  def diff(src: File, tgt: File): String = diff(NORMAL, src, tgt)

  def diff(O: ASCIIDiffOption.Value, src: File, tgt: File): String = O match {
    case NORMAL =>
      diff(O, src.content, tgt.content)
    case UNIFIED =>
      val formatter = new java.text.SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSSSSSSSS Z")
      val buf = new StringBuilder
      buf append "--- " append src.ap append " " append formatter.format(new java.util.Date())
      buf append "\n"
      buf append "+++ " append tgt.ap append " " append formatter.format(new java.util.Date())
      buf append "\n"
      buf append diff(O, src.content, tgt.content)
      buf.toString
  }

  def diff(src: String, tgt: String): String = diff(NORMAL, src, tgt)

  def diff(O: ASCIIDiffOption.Value, src: String, tgt: String): String =
    new Differ[String](src.linesWithSeparators.toList, tgt.linesWithSeparators.toList).diff(O)
}

/** Primitive, ie. without any optimization, implementation of GNU diff. 
 *  <p>cf. <a href="http://en.wikipedia.org/wiki/Longest_common_subsequence_problem">LCS</a></p>. 
 *  @author  <a href="mailto:normen.mueller@googlemail.com">Normen M&#xFC;ller</a>
 *  @version 0.0.6
 */
private[text] class Differ[T <% Ordered[T]](X: List[T], Y: List[T]) {
  import scala.collection.immutable.{ SortedMap, TreeMap }

  def diff(O: ASCIIDiffOption.Value): String = O match {
    case NORMAL => normal(ed(bt(lcs(), X, Y, X.length, Y.length, TreeMap.empty[Int, Int])))
    case UNIFIED => unified(ed(bt(lcs(), X, Y, X.length, Y.length, TreeMap.empty[Int, Int])))
  }

  /* build lcs table */
  private def lcs(): Array[Array[Int]] = {
    val C: Array[Array[Int]] = Array.ofDim(X.length + 1, Y.length + 1)
    for (i <- 1 to X.length)
      for (j <- 1 to Y.length)
        if (X(i - 1) == Y(j - 1))
          C(i)(j) = C(i - 1)(j - 1) + 1
        else C(i)(j) = C(i)(j - 1) max C(i - 1)(j)
    C
  }

  /* back-trace all */
  private def bt(C: Array[Array[Int]], X: List[T], Y: List[T], i: Int, j: Int, m: SortedMap[Int, Int]): SortedMap[Int, Int] = {
    if (i == -1 || j == -1)
      m
    else if ((X isDefinedAt i) && (Y isDefinedAt j) && X(i) == Y(j))
      if (m.keySet.exists(k => m(k) == j && k < i))
        m
      else bt(C, X, Y, i - 1, j - 1, ((n: SortedMap[Int, Int]) => n -- (n.keySet filter (k => n(k) == j && k > i)))(m + { (i, j) }))
    else {
      var n: SortedMap[Int, Int] = m
      if (i > 0 && j > 0 && C(i)(j - 1) >= C(i - 1)(j))
        n = bt(C, X, Y, i, j - 1, n)
      if (i > 0 && j > 0 && C(i - 1)(j) >= C(i)(j - 1))
        n = bt(C, X, Y, i - 1, j, n)
      n
    }
  }

  /* build edit script */
  import scala.collection.mutable.ListBuffer
  private def ed(m: SortedMap[Int, Int]): List[Delta] = {
    var xi = 0
    var yi = 0
    var pending: Option[Delta] = None
    val ds = new ListBuffer[Delta]()
    while (xi <= { if (m.size == 0) 0 else 1 + m.lastKey } - 1) {
      if (m contains xi) {
        while (yi < m(xi)) {
          pending = onBNotA(pending, xi, yi)
          yi += 1
        }
        pending = onMatch(ds, pending, xi, yi)
        yi += 1
      } else pending = onANotB(pending, xi, yi)
      xi += 1
    }
    while (xi < X.length || yi < Y.length) {
      if (xi == X.length && yi < Y.length) while (yi < Y.length) { pending = onBNotA(pending, xi, yi); yi += 1 }
      if (yi == Y.length && xi < X.length) while (xi < X.length) { pending = onANotB(pending, xi, yi); xi += 1 }
      if (xi < X.length) { pending = onANotB(pending, xi, yi); xi += 1 }
      if (yi < Y.length) { pending = onBNotA(pending, xi, yi); yi += 1 }
    }
    pending match {
      case Some(p) => ds += p; ds.toList
      case None => ds.toList
    }
  }

  private def onANotB(pending: Option[Delta], x: Int, y: Int): Option[Delta] = pending match {
    case Some(Delta(ds, de, as, ae)) => Some(Delta(x min ds, x max de, as, ae))
    case None => Some(Delta(x, x, y, -1))
  }

  private def onBNotA(pending: Option[Delta], x: Int, y: Int): Option[Delta] = pending match {
    case Some(Delta(ds, de, as, ae)) => Some(Delta(ds, de, y min as, y max ae))
    case None => Some(Delta(x, -1, y, y))
  }

  private def onMatch(ds: ListBuffer[Delta], pending: Option[Delta], x: Int, y: Int): Option[Delta] = pending match {
    case Some(p) => ds += p; None
    case None => pending
  }

  /* slurp edit script into string representation (GNU diff normal output format)
   * @todo That has to go even more beautiful in particular the "\n---\n" part. */
  private def normal(ds: List[Delta]): String = (new StringBuilder /: ds)((b, d) => {
    b append { if (d.delEnd == -1) d.delStart else 1 + d.delStart } append {
      if (d.delEnd != -1 && d.delStart != d.delEnd)
        "," + (1 + d.delEnd)
      else ""
    }
    b append { if (d.delEnd != -1 && d.addEnd != -1) "c" else if (d.delEnd == -1) "a" else "d" }
    b append { if (d.addEnd == -1) d.addStart else 1 + d.addStart } append {
      if (d.addEnd != -1 && d.addStart != d.addEnd)
        "," + (1 + d.addEnd)
      else ""
    }
    b append "\n"
    b append {
      if (d.delEnd != -1) {
        //X.slice(d.delStart,d.delEnd+1).mkString("< ", "< ", "") + {if(d.addEnd != -1) "---\n" else ""}
        ((s: List[T]) => {
          val last = s.last.toString
          s.mkString("< ", "< ", "") + {
            if (d.addEnd != -1) {
              if (last.charAt(last.length - 1) == '\n')
                "---\n"
              else "\n---\n"
            } else ""
          }
        })(X.slice(d.delStart, d.delEnd + 1))
      } else ""
    }
    b append { if (d.addEnd != -1) Y.slice(d.addStart, d.addEnd + 1).mkString("> ", "> ", "") else "" }
  }).toString

  /* slurp edit script into string representation (GNU diff unified output format) */
  private def unified(ds: List[Delta]): String = (new StringBuilder(
    "@@ -" + {
      if (ds.head.delEnd == 0)
        ds.head.delEnd.abs + 1
      else ds.head.delEnd.abs
    } + "," + (ds.last.delEnd + 1) + " +" + {
      if (ds.head.addStart == 0)
        ds.head.addStart.abs + 1
      else ds.head.addStart.abs
    } + "," + (ds.last.addEnd + 1) + " @@\n") /: ds)((b, d) => {
    b append (X.slice(d.delStart, d.delEnd + 1) match {
      case Nil => ""
      case l@_ => l.mkString("-", "-", "") + {
        if (d.addEnd == -1)
          X.slice(d.addStart, d.addStart + 1).mkString(" ", " ", "")
        else ""
      }
    })
    b append (Y.slice(d.addStart, d.addEnd + 1) match {
      case Nil => ""
      case l@_ => l.mkString("+", "+", "") + {
        if (d.delEnd == -1)
          X.slice(d.addStart, d.addEnd).mkString(" ", " ", "")
        else ""
      }
    })
  }).toString
}

private[text] case class Delta(var delStart: Int, var delEnd: Int, var addStart: Int, var addEnd: Int)
